import heapq
import pandas as pd
from collections import defaultdict

# 从Excel文件读取罗马尼亚地图和启发函数数据 - 修改版本
def read_data_from_excel(file_path):
    print("开始从Excel文件读取数据...")
    
    try:
        # 读取第一个工作表(sheet1)中的距离矩阵
        print("正在从Sheet1读取邻接矩阵...")
        distance_df = pd.read_excel(file_path, sheet_name=0, header=0, index_col=0)
        print(f"邻接矩阵读取成功! 形状: {distance_df.shape}")
        
        # 读取第二个工作表(sheet2)中的启发函数值 - 修改header参数确保读取第一行
        print("正在从Sheet2读取启发函数值...")
        heuristic_df = pd.read_excel(file_path, sheet_name=1)  # sheet_name=1
        print(f"启发函数值读取成功! 形状: {heuristic_df.shape}")
        
        return distance_df, heuristic_df
    
    except Exception as e:
        print(f"读取Excel数据失败: {str(e)}")
        raise


def create_romania_map(distance_df):
    graph = defaultdict(list) # 使用defaultdict简化邻接表的创建
    print("开始构建罗马尼亚地图...")
    connections_count = 0
    
    # 根据距离矩阵构建邻接表
    for city1 in distance_df.index:
        for city2 in distance_df.columns:
            # 获取距离值并确保它是一个标量
            try:
                distance = distance_df.loc[city1, city2]
                # 使用标量比较方法而不是直接使用 != 运算符
                if isinstance(distance, (int, float)):
                    if distance != 1000:
                        graph[city1].append((city2, distance))
                        connections_count += 1
                else:
                    # 如果是Series，转换为标量后比较
                    distance_val = distance.iloc[0] if hasattr(distance, 'iloc') else float(distance)
                    if distance_val != 1000:
                        graph[city1].append((city2, distance_val))
                        connections_count += 1
            except Exception as e:
                print(f"处理城市 {city1} 到 {city2} 的连接时出错: {e}")
    
    print(f"罗马尼亚地图构建完成! 共有 {len(graph)} 个城市, {connections_count} 条连接")
    return graph

# 构建到布加勒斯特的启发函数
def build_heuristic_function(heuristic_df):
    heuristic = {}
    print("开始构建启发函数...")
    
    # 读取城市名和启发函数值
    count = 0
    for i in range(len(heuristic_df)):
        try:
            city = heuristic_df.iloc[i, 0]  # 第一列是城市名
            value = heuristic_df.iloc[i, 1]  # 第二列是启发函数值
            if pd.notna(city) and pd.notna(value):
                heuristic[city] = value
                count += 1
        except Exception as e:
            print(f"处理启发函数的第 {i} 行时出错: {e}")
    
    print(f"启发函数构建完成! 共加载了 {count} 个城市的启发值")
    
    # 打印部分启发函数值作为调试信息
    if heuristic:
        print("部分启发函数值示例:")
        items = list(heuristic.items())[:5]
        for city, value in items:
            print(f"  {city}: {value}")
    
    return heuristic

# 添加三个搜索算法函数定义
# 1. 代价一致搜索（统一代价搜索）
def uniform_cost_search(graph, start, goal):
    # 优先队列中的元素为 (路径代价, 城市, 路径)
    priority_queue = [(0, start, [start])] # 初始化优先队列
    visited = set() # 已访问的节点集合
    expanded = 0 # 扩展的节点计数
    
    while priority_queue:
        cost, current, path = heapq.heappop(priority_queue)
        expanded += 1
        
        if current == goal:
            return path, cost, expanded
        
        if current in visited:
            continue
        
        visited.add(current)
        
        for neighbor, step_cost in graph[current]:
            if neighbor not in visited:
                new_cost = cost + step_cost
                new_path = path + [neighbor]
                heapq.heappush(priority_queue, (new_cost, neighbor, new_path))
    
    return None, None, expanded  # 没有找到路径

# 2. 贪婪算法（贪婪最佳优先搜索）
def greedy_search(graph, start, goal, h):
    # h 是一个字典，包含每个城市到目标城市的启发式距离
    # 优先队列中的元素为 (启发式距离, 城市, 路径, 总代价)
    priority_queue = [(h[start], start, [start], 0)]
    visited = set()
    expanded = 0
    
    while priority_queue:
        _, current, path, cost = heapq.heappop(priority_queue) # 初始化优先队列
        expanded += 1
        
        if current == goal:
            return path, cost, expanded
        
        if current in visited:
            continue
        
        visited.add(current)
        
        for neighbor, step_cost in graph[current]:
            if neighbor not in visited:
                new_cost = cost + step_cost
                new_path = path + [neighbor]
                heapq.heappush(priority_queue, (h[neighbor], neighbor, new_path, new_cost))
    
    return None, None, expanded  # 没有找到路径

# 3. A*算法
def a_star_search(graph, start, goal, h):
    # 优先队列中的元素为 (总评估代价, 城市, 路径, 已走路径代价)
    
    priority_queue = [(h[start], start, [start], 0)]
    visited = set()
    expanded = 0
    
    while priority_queue:
        _, current, path, cost_so_far = heapq.heappop(priority_queue)
        expanded += 1
        
        if current == goal:
            return path, cost_so_far, expanded
        
        if current in visited:
            continue
        
        visited.add(current)
        
        for neighbor, step_cost in graph[current]:
            if neighbor not in visited:
                new_cost = cost_so_far + step_cost
                new_path = path + [neighbor]
                # f(n) = g(n) + h(n)，g(n)是已走代价，h(n)是启发式估计
                f = new_cost + h[neighbor]
                heapq.heappush(priority_queue, (f, neighbor, new_path, new_cost))
    
    return None, None, expanded  # 没有找到路径

# 主函数 - 添加更多调试信息
def main():
    # Excel文件路径
    file_path = r"罗马尼亚度假问题地图及启发函数值.xlsx"
    
    try:
        # 读取Excel数据
        distance_df, heuristic_df = read_data_from_excel(file_path)
        
        # 添加调试信息
        print("\n距离矩阵的形状:", distance_df.shape)
        print("距离矩阵的前几行:")
        print(distance_df.head())
        
        print("\n启发函数数据的形状:", heuristic_df.shape)
        print("启发函数数据的前几行:")
        print(heuristic_df.head())
        
        # 构建罗马尼亚地图
        romania_map = create_romania_map(distance_df)
        
        # 构建启发函数
        heuristic = build_heuristic_function(heuristic_df)
        
        start_city = "Arad"
        goal_city = "Bucharest"
        
        # 验证起点和终点在图中
        print(f"\n验证起点和终点...")
        if start_city not in romania_map:
            print(f"错误: 起点 '{start_city}' 不在地图中!")
            return
        else:
            print(f"起点 '{start_city}' 验证成功!")
            
        if goal_city not in heuristic:
            print(f"错误: 终点 '{goal_city}' 不在启发函数中!")
            return
        else:
            print(f"终点 '{goal_city}' 验证成功!")
        
        print("\n罗马尼亚度假问题 - 从{}到{}的路径搜索".format(start_city, goal_city))
        print("=" * 50)
        
        # 打印地图信息
        print("\n地图信息:")
        print("城市数量:", len(romania_map))
        print("连接数量:", sum(len(neighbors) for neighbors in romania_map.values()))
        
        # 1. 代价一致搜索
        print("\n执行代价一致搜索...")
        path, cost, expanded = uniform_cost_search(romania_map, start_city, goal_city)
        print("\n1. 代价一致搜索结果:")
        if path:
            print("路径:", " -> ".join(path))
            print("总代价:", cost)
            print("扩展节点数:", expanded)
        else:
            print("未找到路径!")
            print("扩展节点数:", expanded)
        
        # 2. 贪婪算法
        print("\n执行贪婪算法搜索...")
        path, cost, expanded = greedy_search(romania_map, start_city, goal_city, heuristic)
        print("\n2. 贪婪算法搜索结果:")
        if path:
            print("路径:", " -> ".join(path))
            print("总代价:", cost)
            print("扩展节点数:", expanded)
        else:
            print("未找到路径!")
            print("扩展节点数:", expanded)
        
        # 3. A*算法
        print("\n执行A*算法搜索...")
        path, cost, expanded = a_star_search(romania_map, start_city, goal_city, heuristic)
        print("\n3. A*算法搜索结果:")
        if path:
            print("路径:", " -> ".join(path))
            print("总代价:", cost)
            print("扩展节点数:", expanded)
        else:
            print("未找到路径!")
            print("扩展节点数:", expanded)
            
    except Exception as e:
        print("执行过程中发生错误:", str(e))
        import traceback
        traceback.print_exc()

if __name__ == "__main__":
    main()